package com.huawei.tree.threaded_binary_tree;

//实现了线索化功能的二叉树
public class ThreadedBinaryTree {
    private ThreadedHeroNode root;

    //为了实现线索化，需要创建当前节点的前驱结点的指针
    //递归进行线索化时，保留前一个节点
    private ThreadedHeroNode pre = null;

    public void setRoot(ThreadedHeroNode root) {
        this.root = root;
    }

    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        }else {
            System.out.println("二叉树为空，不能遍历");
        }
    }

    //中序遍历
    public void midOrder() {
        if (this.root != null) {
            this.root.midOrder();
        }else {
            System.out.println("二叉树为空，不能遍历");
        }
    }

    //后序遍历
    public void afterOrder() {
        if (this.root != null) {
            this.root.afterOrder();
        }else {
            System.out.println("二叉树为空，不能遍历");
        }
    }

    //前序遍历查找
    public ThreadedHeroNode preOrderSearch(int no) {
        return this.root.preOrderSearch(no);
    }

    //中序遍历查找
    public ThreadedHeroNode midOrderSearch(int no) {
        return this.root.midOrderSearch(no);
    }

    //后序遍历查找
    public ThreadedHeroNode afterOrderSearch(int no) {
        return this.root.afterOrderSearch(no);
    }

    //递归删除节点（规定1）
    public void delNode1(int no) {
        if (this.root != null && this.root.getNo() == no) {
            this.root = null;
            return;
        }
        this.root.delNode1(no);
    }

    //递归删除节点（规定2）
    public void delNode2(int no) {
        if (this.root != null && this.root.getNo() == no) {
            if (this.root.getLeft() != null) {
                this.root = this.root.getLeft();
                return;
            }
            if (this.root.getRight() != null) {
                this.root = this.root.getRight();
                return;
            }
        }
        this.root.delNode2(no);
    }

    /**
     * @Name: 前序线索化二叉树
     * @Author: GaoJian
     * @Date: 2022/4/17 15:28
     * @Description: 参数为需要线索化的节点
     */
    public void preOrderThreadedNode(ThreadedHeroNode node) {
        //如果node为null，不能线索化
        if (node == null) {
            return;
        }

        //（一）线索化当前节点
        //1、处理当前节点的前驱节点
        if (node.getLeft() == null) {
            //让当前节点的左指针指向前驱节点
            node.setLeft(pre);
            //修改当前节点的左指针的类型
            node.setLeftType(1);
        }
//        //2、处理后继节点：
//        //说明：前序遍历的左子节点的后一个节点是它的兄弟
//        //     前序遍历的右子节点的后一个节点是它父节点的兄弟
//        //（1）帮它的前一个节点处理后继节点
//        if (pre != null && pre.getRight() == null) {
//            //拿到当前节点，对上一个节点的后继节点进行处理
//            pre.setRight(node);
//            //修改指针类型
//            pre.setRightType(1);
//        }
//        //（2）帮它的左子节点处理后继节点
//        if (node.getLeft() != null && node.getLeft().getLeft() == null) {
//            //将该节点的左子节点的后继节点设为该节点的右子节点
//            node.getLeft().setRight(node.getRight());
//            //指针修改类型
//            node.getLeft().setRightType(1);
//        }
//        //3、处理完当前节点后，要处理下一个节点，pre变为当前节点
//        pre = node;
        //2、处理后继节点：中序遍历的后继节点是当前节点的父节点（或者父节点的父节点）
        //当前节点无法获取到当前节点的父节点（或者父节点的父节点），只能在当前节点对上一个节点进行后继节点处理
        if (pre != null && pre.getRight() == null) {
            //拿到当前节点，对上一个节点的后继节点进行处理
            pre.setRight(node);
            pre.setRightType(1);
        }
        //3、处理完当前节点后，要处理下一个节点，pre变为当前节点
        pre = node;

        //（二）线索化左子树
        if (node.getLeftType() == 0) {
            preOrderThreadedNode(node.getLeft());
        }

        //（三）线索化右子树
        preOrderThreadedNode(node.getRight());
    }

    public void preOrderThreadedNode() {
        preOrderThreadedNode(root);
    }

    /**
     * @Name: 中序线索化二叉树
     * @Author: GaoJian
     * @Date: 2022/4/17 14:40
     * @Description: 参数为需要线索化的节点
     */
    public void midOrderThreadedNodes(ThreadedHeroNode node) {
        //如果node为null，不能线索化
        if (node == null) {
            return;
        }

        //（一）先线索化左子树
        midOrderThreadedNodes(node.getLeft());

        //（二）线索化当前节点
        //1、处理当前节点的前驱节点
        if (node.getLeft() == null) {
            //让当前节点的左指针指向前驱节点
            node.setLeft(pre);
            //修改当前节点的左指针的类型
            node.setLeftType(1);
        }
        //2、处理后继节点：中序遍历的后继节点是当前节点的父节点（或者父节点的父节点）
        //当前节点无法获取到当前节点的父节点（或者父节点的父节点），只能在当前节点对上一个节点进行后继节点处理
        if (pre != null && pre.getRight() == null) {
            //拿到当前节点，对上一个节点的后继节点进行处理
            pre.setRight(node);
            pre.setRightType(1);
        }
        //3、处理完当前节点后，要处理下一个节点，pre变为当前节点
        pre = node;

        //（三）再线索化右子树
        midOrderThreadedNodes(node.getRight());
    }

    public void midOrderThreadedNodes() {
        midOrderThreadedNodes(root);
    }

    /**
     * @Name: 后序线索化二叉树
     * @Author: GaoJian
     * @Date: 2022/4/17 15:29
     * @Description: 参数为需要线索化的节点
     */
    public void afterOrderThreadedNode(ThreadedHeroNode node) {
        //如果node为null，不能线索化
        if (node == null) {
            return;
        }

        //（一）线索化左子树
        afterOrderThreadedNode(node.getLeft());

        //（二）线索化右子树
        afterOrderThreadedNode(node.getRight());

        //（三）线索化当前节点
        //1、处理当前节点的前驱结点
        if (node.getLeft() == null) {
            //让当前节点的左指针指向前驱节点
            node.setLeft(pre);
            //修改当前节点的左指针的类型
            node.setLeftType(1);
        }
//        //2、处理后继节点
//        //后序遍历：左->右->父
//        //（1）帮左子节点设置后继
//        if (node.getLeft() != null && node.getLeft().getRight() == null) {
//            node.getLeft().setRight(node.getRight());
//        }
//        //（2）帮右子节点设置后继
//        if (node.getRight() != null && node.getRight().getLeft() == null) {
//            node.getRight().setLeft(node);
//        }
//        //3、处理完当前节点后，要处理下一个节点，pre变为当前节点
//        pre = node;
        //2、处理后继节点：中序遍历的后继节点是当前节点的父节点（或者父节点的父节点）
        //当前节点无法获取到当前节点的父节点（或者父节点的父节点），只能在当前节点对上一个节点进行后继节点处理
        if (pre != null && pre.getRight() == null) {
            //拿到当前节点，对上一个节点的后继节点进行处理
            pre.setRight(node);
            pre.setRightType(1);
        }
        //3、处理完当前节点后，要处理下一个节点，pre变为当前节点
        pre = node;
    }

    public void afterOrderThreadedNode() {
        afterOrderThreadedNode(root);
    }

}
